The open system Interconnection (OSI) reference model of a communications network includes a data link control layer which controls the sharing of the network among the physical end-points. The data link control layer is subdivided into two sub-layers, the logical link control (LLC) sub-layer and the media access control (MAC) sub-layer. The MAC sub-layer uses a unique address to identify each node (end-point) in the system in order to share the network among the entire different end-points of the network. In mobile and ad hoc wireless networks, (MANETs) as well as sensor networks, there is no dedicated or central node that organizes the channel in general and the access to the channel in particular. The MAC system in such networks has to minimize collision phenomena, i.e. the transmission of packets by different nodes so that none of the receiving nodes receives more than one packet at a time, with loss of data. This discussed by R. Rozovsky and P. R. Kumar, “Seedex: a MAC protocol for ad hoc networks”, The ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 67-75, 2001 the contents of which are incorporated herein by reference. Another requirement from such MAC systems is that they support broadcast messages (i.e., one-to-many), and be quality of service (QoS) aware, such as by providing delay guarantee, as discussed by V. R. Syrotiuk, Charles J. Colbourn and Alan C. H. Ling, “Topology-Transparent Scheduling for MANETs using Orthogonal Arrays”, DIAL-M/POMC 2003: San Diego, Calif., USA, pp 43-49, 2003, the contents of which are incorporated herein by reference.
An ad hoc wireless communications network is a wireless network having no central organizing node or a pre-defined infrastructure. Usually, all the participating nodes are to make decisions and all nodes within the range of a transmitting node receive packets from aforementioned node. Typically, the invention is implemented in ad hoc wireless networks in which each node is unaware of the total network topology; rather it utilizes for each node the local topology. Therefore, in the context of the environment in which the present invention is implemented even as nodes are referred to as interacting in the network, in fact only a topologically defined fraction of the network which is relevant for each node. Such a network was presented by L. Bao and J. J. Garcia-Luna-Aceves, “Distributed Dynamic Channel Access Scheduling for ad hoc Networks”, Journal of Parallel and Distributed Computing, Volume 63, pp. 3-14, January 2003, the contents of which are incorporated herein by reference. In such a network, the MAC system is also distributed among some or all of the participating nodes. In a wireless communications channel of the invention, the distribution mode of time slots S1 . . . Sn is known to the various nodes. The slots are available to Mynode in compliance with rules, some of which will be discussed below. A set of nodes (end-points), optionally mobile in space, are listed in Mynode's node database. Each such node if defined as potential interfering node is potentially capable of sending a message, at any slot along the time axis and such a message may collide with Mynode's message if it is sent at the same time. In the network discussed hereinbefore, other nodes are possibly participating, which are not listed in Mynode's node database and are therefore not considered as potential interfering nodes. Mynode's MAC element invokes a slot scheduler, such that only one of the nodes listed Mynode's node data base can send a message to the contemporary slot. The number of nodes stored in Mynode's node database may be dynamic, but every node possesses a unique ID.
The environment in which the present invention is implemented is that of an ad hoc communications network using one or more single time-slotted channels in which the nodes are dynamically allocated shares of the available bandwidth in one channel. The invention relates to service in which the messages sent by the nodes are broadcast messages, meaning that a packet sent by a node can be potentially received by all its node neighbors. Each node uses an omni-directional antenna capable of potentially interconnecting with all its node neighbors. Due to bandwidth limitations, the available bandwidth is shared between nodes in correlation with the bandwidth demand of each node. The average time-slot (TS) rate that a node demands for transmission is referred to as TS refresh rate. A node with a high TS refresh rate demands more bandwidth from the available bandwidth than a node with a lower refresh rate. An example for such nodes bandwidth sharing is described as follows. In a road traffic control system, Myvehicle updates its own vehicle database in order to avoid road accidents. The other vehicles potentially capable of intercepting Myvehicle send position messages in frequency correlated with their velocity. The faster a vehicle travels the more frequent the update signal is sent to the potentially susceptible vehicle.
Typically the service implements a multi-hop routing. Unlike some ad hoc communications systems using one hop or two hop routing, the network of the present invention is not restricted to two hop routing and three or even higher hop levels can be implemented. In all hop levels, the system is to prevent or minimize collision phenomena in broadcast messages, i.e. the transmitting of packets by different nodes so that receiving nodes do not receive more than one packet at once from different senders, causing loss of data. To more elaborately explain the access of node to time slots in a channel, reference is made to FIG. 1 which describes a slot selecting system as known in the art. Time slotted wireless communications channel 20 has time slots (TSs) S1 . . . Sn. Time slot characteristics and distribution along the time axis are known to all nodes. The TSs are available to any node in compliance with the rules governing the access to the slots, some of which will be discussed below. The distribution of nodes in space may be randomized and dynamic, affecting the connectivity of the nodes with Mynode and with other nodes. A node database in Mynode contains the list of the IDs of nodes which are likely to inter-collide in slots of the channel. For example, in U.S. Pat. No. 5,396,644, the contents of which are incorporated herewith by reference, a node stores data of its near neighbours and the neighbours of each neighbour (two-hop neighbours), and whenever it sends a neighbour update signal, it sends also a list of near neighbours. This way, each node is always kept updated as of the list of neighbours and the neighbours of each neighbour. This provides ground for a two-hop routing level capability. Generally the node ID database is responsible for optional functional disappearance or reappearance or appearance of nodes. The function for selecting a certain node to transmit at a certain TS considers all the node databases of all nodes which are likely to inter-collide in slots of the channel. The communication network, before each upcoming TS invokes the selection function that determines which is the one node to transmit in the upcoming TS. The function is referred to hereinafter as a “which node is to transmit in the next TS” (WINIT). The function takes into account all the ID available in the node databases of the different nodes associated with the node DB in each node and the WINIT function is activated in each node and for all time slots.
Othernode 30 which is one of the candidates for transmitting in time slot 32, will send packets at time slot 32 only when WINIT function 34 of the local MAC element 36 of othernode 30 orders it to do so. The WINIT, a function of the MAC, receives the actual time (i.e. time slot number) and the list nodes which are likely to inter-collide in slots of the channel. All the nodes activate their slot scheduler, but only one will transmit at the current time slot. Thus, in time slot 40 Mynode 42 is active sending a packet. MAC element 44 of Mynode invokes mynode WINIT 46. Whereas all the other nodes listed in Mynode's database 48, some or all of which request to transmit at that time slot, remain mute with respect to TS 40.